package 力扣._00周赛._370周赛.问题3;

import java.util.*;

public class Solution {
    long[] postOrder(int v, int n, Map<Integer, Set<Integer>> edges, int[] values, boolean[] visited) {
        //是否是叶子节点
        boolean last = true;
        visited[v] = true;
        for (int i = 0; i < n; i++) {
            if (edges.get(v).contains(i) && !visited[i]) {
                last = false;
                break;
            }
        }
        if (last)//是叶节点
            return new long[]{0, values[v]};
        //非叶节点
        List<long[]> list = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (edges.get(v).contains(i) && !visited[i]) {
                visited[i] = true;
                long[] p = postOrder(i, n, edges, values, visited);
                list.add(p);
            }
        }

        //dp
        //当前子树最大健康和
        long v1 = 0;

        long t1 = values[v]; //选当前+=各子树最大健康值
        long t2 = 0;         //不选当前+=各子树最大值
        for (long[] d : list) {
            t1 += d[0];
            t2 += d[1];
        }
        v1 = Math.max(t1, t2);

        //当前子树全选
        long v2 = values[v];
        for (long[] d : list) {
            v2 += d[1];
        }
        return new long[]{v1, v2};

    }


    public long maximumScoreAfterOperations(int[][] edges, int[] values) {
        //dp[i][0]: 当前子树最大健康和
        //dp[i][1]: 当前子树全选
        //dp[i][0] = dp[
        //edge邻接表示会内存超出限制
        int n = values.length;
        boolean[] visited = new boolean[n];
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int[] e : edges) {
            if (map.containsKey(e[0]))
                map.get(e[0]).add(e[1]);
            else {
                map.put(e[0], new HashSet<>());
                map.get(e[0]).add(e[1]);
            }
            if (map.containsKey(e[1]))
                map.get(e[1]).add(e[0]);
            else {
                map.put(e[1], new HashSet<>());
                map.get(e[1]).add(e[0]);
            }
        }
        long[] p = postOrder(0, n, map, values, visited);
        return p[0];
    }

    public static void main(String[] args) {
        int[][] e = new int[][]{{0, 1}, {0, 2}, {0, 3}, {2, 4}, {4, 5}};
        int[] v = new int[]{5, 2, 5, 2, 1, 1};
        long l = new Solution().maximumScoreAfterOperations(e, v);
        System.out.println(l);
    }
}
